import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-11-05
 * Time: 19:41
 */
public class Solution {
//     方法一: 二分查找
//     先固定 x, 对 y 进行二分
    public List<List<Integer>> findSolution1(CustomFunction customfunction, int z) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 1; i <= 1000; i++) {
            // 这里面注意 x, y 与 y, x 是不同的, 所以 y 的范围也是 [1, 1000]
            int left = 1;
            int right = 1000;
            while (left <= right) {
                int mid = ((right-left) >> 1) + left;
                int val = customfunction.f(i, mid);
                if (val == z) {
                    ans.add(new ArrayList<>(Arrays.asList(i, mid)));
                    break;
                } else if (val < z) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            }
        }
        return ans;
    }


//     方法二: 双指针
//     x1, y1 == x2, y2
//     那么 当 x1 < x2 时 y1 > y2
//     所以就可以使用双指针
//     从小到大遍历 x, 从大到小遍历 y
    public List<List<Integer>> findSolution2(CustomFunction customfunction, int z) {
        List<List<Integer>> ans = new ArrayList<>();
        int y = 1000;
        for (int x = 1; x <= 1000; x++) {
            while (y >= 1 && customfunction.f(x, y) > z) {
                y--;
            }
            if (y >= 1 && customfunction.f(x, y) == z) {
                ans.add(new ArrayList<Integer>(Arrays.asList(x, y)));
            }
        }
        return ans;
    }
}
